Fibonacci word

A Fibonacci word is a specific sequence of binary digits (or symbols from any two-letter alphabet). The Fibonacci word is formed by repeated concatenation in the same way that the Fibonacci numbers are formed by repeated addition.

It is a paradigmatic example of a Sturmian word.

The name “Fibonacci word” has also been used to refer to the members of a formal language L consisting of strings of zeros and ones with no two repeated ones. Any prefix of the specific Fibonacci word belongs to L, but so do many other strings. L has a Fibonacci number of members of each possible length.

Contents

Definition

Let S_0 be "0" and S_1 be "01". Now S_n = S_{n-1}S_{n-2} (the concatenation of the previous sequence and the one before that).

The infinite Fibonacci word is the limit S_{\infty}.

The Fibonacci words

We have:

S_0    0

S_1    01

S_2    010

S_3    01001

S_4    01001010

S_5    0100101001001

...

The first few elements of the infinite Fibonacci word are:

0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, ...

Closed-form expression for individual digits

The nth digit of the word is 2%2B\left\lfloor {\left( {n %2B 1} \right)\,\varphi} \right\rfloor - \left\lfloor {\left( {n %2B 2} \right)\,\varphi } \right\rfloor where \varphi is the golden ratio and \left\lfloor x \right\rfloor is the floor function (sequence A003849 in OEIS).

Substitution rules

Another way of going from Sn to Sn + 1 is to replace each symbol 0 in Sn with the pair of consecutive symbols 0, 1 in Sn + 1, and to replace each symbol 1 in Sn with the single symbol 0 in Sn + 1.

Alternatively, one can imagine directly generating the entire infinite Fibonacci word by the following process: start with a cursor pointing to the single digit 0. Then, at each step, if the cursor is pointing to a 0, append 1, 0 to the end of the word, and if the cursor is pointing to a 1, append 0 to the end of the word. In either case, complete the step by moving the cursor one position to the right.

A similar infinite word, sometimes called the rabbit sequence, is generated by a similar infinite process with a different replacement rule: whenever the cursor is pointing to a 0, append 1, and whenever the cursor is pointing to a 1, append 0, 1. The resulting sequence begins

0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, ...

However this sequence differs from the Fibonacci word only trivially, by swapping 0's for 1's and shifting the positions by one.

Discussion

The word is related to the famous sequence of the same name (the Fibonacci sequence) in the sense that addition of integers in the inductive definition is replaced with string concatenation. This causes the length of Sn to be Fn + 2, the (n + 2)th Fibonacci number. Also the number of 1s in Sn is Fn and the number of 0s in Sn is Fn + 1.

Other properties

Applications

Modern Crystal growth techniques have been used by Merlin et al., and Dharma-wardana et al., to grow one-dimensional Fibonacci crystals, and study their light scattering properties. [2]

References

  1. ^ de Luca, Aldo (1995), "A division property of the Fibonacci word", Information Processing Letters 54 (6): 307–312, doi:10.1016/0020-0190(95)00067-M. 
  2. ^ Chandre Dharma-wardana et al., (1987). Physical Review Letters (58): 1761–1765. 

External links